#pragma once
#include "Integer.h"
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>

template <typename T> class Polynomial: public std::vector<T>
{
public:
	Polynomial() {}
	Polynomial(const T &n)
	{
		if (n != 0)
			this->push_back(n);
	}
	Polynomial(const typename std::vector<T> &vec): std::vector<T>(vec)
	{
		while (this->size() && this->back() == 0)
			this->pop_back();
	}
	Polynomial(const typename Polynomial::const_iterator &begin, const typename Polynomial::const_iterator &end)
	: std::vector<T>(begin, end) {}
private:
	static char variable;
	static unsigned printOptions;
public:
	static const unsigned Default = 0x00;
	static const unsigned AscendingOrder = 0x01;
	static const unsigned PreserveZeroTerms = 0x02;
	static const unsigned PrintOne = 0x04;
	static const unsigned PrintAddWhileNegative = 0x08;
public:
	friend unsigned Degree(const Polynomial<T> &poly)
	{
		return poly.size() ? poly.size() - 1 : 0;
	}
	const T LeadingCoefficient() const
	{
		return this->size() ? this->back() : T(0);
	}
	static void SetVariable(const char v)
	{
		Polynomial::variable = v;
	}
	static void SetPrintOptions(const unsigned opt)
	{
		Polynomial::printOptions = opt;
	}
	std::string str() const
	{
		std::ostringstream str;
		const unsigned size = this->size();

		if (size == 0)
			str << T();
		else if (size == 1)
			str << this->front();
		else
		{
			bool alreadyprinted = false;

			if (Polynomial::printOptions & Polynomial::AscendingOrder)
			{
				if (this->front() != T(0) || (Polynomial::printOptions & Polynomial::PreserveZeroTerms))
				{
					str << this->front();
					alreadyprinted = true;
				}

				for (unsigned deg = 1; deg < size; ++deg)
				{
					if ((*this)[deg] == T(0))
					{
						if (!(Polynomial::printOptions & Polynomial::PreserveZeroTerms))
							continue;

						if (alreadyprinted)
							str << " + ";

						str << "0 * x";

						if (deg > 1)
							str << "^" << deg;
					}
					else
					{
						if ((*this)[deg] < T(0) && !(Polynomial::printOptions & Polynomial::PrintAddWhileNegative))
						{
							if (!alreadyprinted)
							{
								alreadyprinted = true;
								str << "-";

								if ((*this)[deg]!= T(-1) || (Polynomial::printOptions & Polynomial::PrintOne))
									str << -(*this)[deg] << " * ";
							}
							else
							{
								str << " - ";

								if ((*this)[deg] != T(-1) || (Polynomial::printOptions & Polynomial::PrintOne))
									str << -(*this)[deg] << " * ";
							}
						}
						else
						{
							if (alreadyprinted)
								str << " + ";
							else
								alreadyprinted = true;

							if ((*this)[deg] != T(1) || (Polynomial::printOptions & Polynomial::PrintOne))
								str << (*this)[deg] << " * ";
						}

						str << "x";

						if (deg > 1)
							str << "^" << deg;
					}
				}
			}
			else
			{
				for (unsigned deg = size - 1; deg > 0; --deg)
				{
					if ((*this)[deg] == T(0))
					{
						if (!(Polynomial::printOptions & Polynomial::PreserveZeroTerms))
							continue;

						if (alreadyprinted)
							str << " + ";

						str << "0 * x";

						if (deg > 1)
							str << "^" << deg;
					}
					else
					{
						if (!(Polynomial::printOptions & Polynomial::PrintAddWhileNegative) && (*this)[deg] < T(0))
						{
							if (!alreadyprinted)
							{
								alreadyprinted = true;
								str << "-";

								if ((*this)[deg] != T(-1) || (Polynomial::printOptions & Polynomial::PrintOne))
									str << -(*this)[deg] << " * ";
							}
							else
							{
								str << " - ";

								if ((*this)[deg] != T(-1) || (Polynomial::printOptions & Polynomial::PrintOne))
									str << -(*this)[deg] << " * ";
							}
						}
						else
						{
							if (alreadyprinted)
								str << " + ";
							else
								alreadyprinted = true;

							if ((*this)[deg] != T(1) || (Polynomial::printOptions & Polynomial::PrintOne))
								str << (*this)[deg] << " * ";
						}

						str << "x";

						if (deg > 1)
							str << "^" << deg;
					}
				}

				if (this->front() == T(0))
				{
					if (Polynomial::printOptions & Polynomial::PreserveZeroTerms)
						str << " + 0";
				}
				else if (!(Polynomial::printOptions & Polynomial::PrintAddWhileNegative) && this->front() < T(0))
					str << " - " << -this->front();
				else
					str << " + " << this->front();
			}
		}

		return str.str();
	}
	friend std::ostream& operator<<(std::ostream &out, const Polynomial &poly)
	{
		return out << poly.str();
	}
	template <typename VarType> const VarType operator()(const VarType &x) const
	{
		VarType sum = VarType();

		for (int i = this->size() - 1; i >= 0; --i)
			sum = sum * x + (*this)[i];

		return sum;
	}
	friend bool operator==(const Polynomial &lhs, const Polynomial &rhs)
	{
		if (lhs.size() != rhs.size())
			return false;

		const unsigned size = lhs.size();

		for (unsigned i = 0; i < size; ++i)
			if (lhs[i] != rhs[i])
				return false;

		return true;
	}
	friend bool operator!=(const Polynomial &lhs, const Polynomial &rhs)
	{
		return !(lhs == rhs);
	}
	friend bool operator<(const Polynomial &lhs, const Polynomial &rhs)
	{
		if (lhs.size() < rhs.size())
			return true;
		else if (lhs.size() > rhs.size())
			return false;

		const unsigned size = lhs.size();

		for (int i = size; --i >= 0;)
		{
			if (lhs[i] < rhs[i])
				return true;
			else if (lhs[i] > rhs[i])
				return false;
		}

		return false;
	}
	friend bool operator<=(const Polynomial &lhs, const Polynomial &rhs)
	{
		return !(rhs > lhs);
	}
	friend bool operator>(const Polynomial &lhs, const Polynomial &rhs)
	{
		return rhs > lhs;
	}
	friend bool operator>=(const Polynomial &lhs, const Polynomial &rhs)
	{
		return !(lhs > rhs);
	}
	Polynomial operator-() const
	{
		Polynomial poly;

		for (const auto &x: *this)
			poly.push_back(-x);

		return std::move(poly);
	}
	friend Polynomial operator+(const Polynomial &lhs, const Polynomial &rhs)
	{
		Polynomial poly;
		const unsigned l1 = lhs.size();
		const unsigned l2 = rhs.size();

		if (l1 < l2)
		{
			poly.reserve(l2);

			for (unsigned i = 0; i < l1; ++i)
				poly.push_back(lhs[i] + rhs[i]);

			for (unsigned i = l1; i < l2; ++i)
				poly.push_back(rhs[i]);
		}
		else if (l1 > l2)
		{
			poly.reserve(l1);

			for (unsigned i = 0; i < l2; ++i)
				poly.push_back(lhs[i] + rhs[i]);

			for (unsigned i = l2; i < l1; ++i)
				poly.push_back(lhs[i]);
		}
		else
		{
			poly.reserve(l1);

			for (unsigned i = 0; i < l1; ++i)
				poly.push_back(lhs[i] + rhs[i]);

			while (poly.size() && poly.back() == T())
				poly.pop_back();
		}

		return std::move(poly);
	}
	Polynomial& operator+=(const Polynomial &poly)
	{
		const unsigned l1 = this->size();
		const unsigned l2 = poly.size();

		if (l1 < l2)
		{
			this->reserve(l2);

			for (unsigned i = 0; i < l1; ++i)
				(*this)[i] += poly[i];

			for (unsigned i = l1; i < l2; ++i)
				this->push_back(poly[i]);
		}
		else if (l1 > l2)
		{
			for (unsigned i = 0; i < l2; ++i)
				(*this)[i] += poly[i];
		}
		else
		{
			for (unsigned i = 0; i < l1; ++i)
				(*this)[i] += poly[i];

			while (this->size() && this->back() == T())
				this->pop_back();
		}

		return *this;
	}
	friend Polynomial operator-(const Polynomial &lhs, const Polynomial &rhs)
	{
		Polynomial poly;
		const unsigned l1 = lhs.size();
		const unsigned l2 = rhs.size();

		if (l1 < l2)
		{
			poly.reserve(l2);

			for (unsigned i = 0; i < l1; ++i)
				poly.push_back(lhs[i] - rhs[i]);

			for (unsigned i = l1; i < l2; ++i)
				poly.push_back(-rhs[i]);
		}
		else if (l1 > l2)
		{
			poly.reserve(l1);

			for (unsigned i = 0; i < l2; ++i)
				poly.push_back(lhs[i] - rhs[i]);

			for (unsigned i = l2; i < l1; ++i)
				poly.push_back(lhs[i]);
		}
		else
		{
			poly.reserve(l1);

			for (unsigned i = 0; i < l1; ++i)
				poly.push_back(lhs[i] - rhs[i]);

			while (poly.size() && poly.back() == T())
				poly.pop_back();
		}

		return std::move(poly);
	}
	Polynomial& operator-=(const Polynomial &poly)
	{
		const unsigned l1 = this->size();
		const unsigned l2 = poly.size();

		if (l1 < l2)
		{
			this->reserve(l2);

			for (unsigned i = 0; i < l1; ++i)
				(*this)[i] -= poly[i];

			for (unsigned i = l1; i < l2; ++i)
				this->push_back(poly[i]);
		}
		else if (l1 > l2)
		{
			for (unsigned i = 0; i < l2; ++i)
				(*this)[i] -= poly[i];
		}
		else
		{
			for (unsigned i = 0; i < l1; ++i)
				(*this)[i] -= poly[i];

			while (this->size() && this->back() == T())
				this->pop_back();
		}

		return *this;
	}
	friend Polynomial operator*(const Polynomial &lhs, const Polynomial &rhs)
	{
		if (lhs == T() || rhs == T())
			return T();

		const unsigned l1 = lhs.size();
		const unsigned l2 = rhs.size();
		Polynomial poly;
		poly.resize(l1 + l2 - 1);

		for (unsigned i = 0; i < l1; ++i)
			for (unsigned j = 0; j < l2; ++j)
				poly[i + j] += lhs[i] * rhs[j];

		return std::move(poly);
	}
	friend Polynomial operator*(const Polynomial &lhs, const T &rhs)
	{
		if (lhs == T() || rhs == T())
			return T();

		Polynomial poly;
		poly.reserve(lhs.size());

		for(const auto &x: lhs)
			poly.push_back(x * rhs);

		return std::move(poly);
	}
	friend Polynomial operator*(const T &lhs, const Polynomial &rhs)
	{
		if (lhs == T() || rhs == T())
			return T();

		Polynomial poly;
		poly.reserve(rhs.size());

		for(const auto &x: rhs)
			poly.push_back(lhs * x);

		return std::move(poly);
	}
	Polynomial operator/(const T &n) const
	{
		if (n == T())
			throw;

		const T inv = Inverse(n);

		if (*this == T())
			return T();

		Polynomial poly;
		poly.reserve(this->size());

		for (const auto &x: *this)
			poly.push_back(x * inv);

		return std::move(poly);
	}
	Polynomial& operator*=(const Polynomial &poly)
	{
		return *this = *this * poly;
	}
	Polynomial& operator*=(const T &n)
	{
		if (*this == T() || n == T())
			return *this = T();

		std::for_each(this->begin, this->end(), [n](T &x) {
			x *= n;
		});
		return *this;
	}
	Polynomial& operator/=(const T &n)
	{
		if (n == T())
			throw;

		if (*this == T())
			return *this;

		const T inv = Inverse(n);
		std::for_each(this->begin, this->end(), [inv](T &x) {
			x *= inv;
		});
		return *this;
	}
	friend Polynomial Square(const Polynomial &poly)
	{
		if (poly == T())
			return T();

		Polynomial sqr;
		sqr.resize((poly.size() << 1) - 1);

		for (unsigned i = 0; i < poly.size(); ++i)
		{
			for (unsigned j = 0; j < i; ++j)
				sqr[i + j] += poly[i] * poly[j] * 2;

			sqr[i << 1] = Square(poly[i]);
		}

		return std::move(sqr);
	}
	friend Polynomial Divide(const Polynomial &lhs, const Polynomial &rhs, Polynomial &remainder)
	{
		if (rhs == Polynomial())
			throw;

		if (lhs.size() < rhs.size())
		{
			remainder = lhs;
			return Polynomial();
		}

		const unsigned size = lhs.size() - rhs.size() + 1;
		Polynomial poly;
		poly.resize(size);
		remainder = lhs;

		for (int i = size; --i >= 0;)
		{
			if (remainder.size() == rhs.size() + i)
			{
				poly[i] = remainder.back() / rhs.back();
				remainder -= (poly[i] * rhs) << i;
			}
			else
				poly[i] = T(0);
		}

		return std::move(poly);
	}
	Polynomial operator/(const Polynomial &poly) const
	{
		Polynomial remainder;
		return Divide(*this, poly, remainder);
	}
	Polynomial& operator/=(const Polynomial &poly)
	{
		Polynomial remainder;
		return *this = Divide(*this, poly, remainder);
	}
	Polynomial operator%(const Polynomial &poly) const
	{
		Polynomial remainder;
		Divide(*this, poly, remainder);
		return std::move(remainder);
	}
	Polynomial& operator%=(const Polynomial &poly)
	{
		Polynomial remainder;
		Divide(*this, poly, remainder);
		this->swap(remainder);
		return *this;
	}
	Polynomial operator<<(const int n) const
	{
		if (n < 0)
			return *this >> static_cast<unsigned>(-n);
		else
			return *this << static_cast<unsigned>(n);
	}
	Polynomial operator<<(const unsigned n) const
	{
		typename std::vector<T> poly(n, T());
		poly.insert(poly.end(), this->begin(), this->end());
		return std::move(poly);
	}
	Polynomial& operator<<=(const int n)
	{
		if (n < 0)
			return *this >>= static_cast<unsigned>(-n);
		else
			return *this <<= static_cast<unsigned>(n);
	}
	Polynomial& operator<<=(const unsigned n)
	{
		this->insert(this->begin(), n, T());
		return *this;
	}
	Polynomial operator>>(const int n) const
	{
		if (n < 0)
			return *this << static_cast<unsigned>(-n);
		else
			return *this >> static_cast<unsigned>(n);
	}
	Polynomial operator>>(const unsigned n) const
	{
		return Polynomial(this->begin() + n, this->end());
	}
	Polynomial& operator>>=(const int n)
	{
		if (n < 0)
			return *this <<= static_cast<unsigned>(-n);
		else
			return *this >>= static_cast<unsigned>(n);
	}
	Polynomial& operator>>=(const unsigned n)
	{
		this->erase(this->begin(), this->begin() + n);
		return *this;
	}
	friend Polynomial Differential(const Polynomial &poly)
	{
		Polynomial deriv;
		const unsigned size = poly.size();

		for (unsigned i = 1; i < size; ++i)
			deriv.push_back(poly[i] * T(i));

		while (deriv.size() && deriv.back() == T(0))
			deriv.pop_back();

		return std::move(deriv);
	}
};

template <typename T> char Polynomial<T>::variable = 'x';
template <typename T> unsigned Polynomial<T>::printOptions = 0;
